import com.sun.source.tree.IfTree;
import com.sun.source.tree.Tree;

public class BinarySearchTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;
    public boolean search(int val){
        if (root==null){
            return false;
        }
        TreeNode cur=root;
        while (cur!=null){
            if (cur.val>val){
                cur=cur.left;
            }else if (cur.val<val){
                cur=cur.right;
            }else {
                return true;
            }
        }
        return false;
    }
    /**
     * 插入
     * 插入的时候如果只有一个指针，当找到该插入的位置的时候，父亲节点找不到无法插入所以需要节点；
     * cur:查找位置节点
     * parent：父亲节点
     */
    public void insert(int val){
        if (root==null){
            root=new TreeNode(val);
            return;
        }
        TreeNode cur=root;
        TreeNode parent=null;
        while (cur!=null){
            if (cur.val>val){
                parent=cur;
                cur=cur.left;
            } else if (cur.val<val) {
                parent=cur;
                cur=cur.right;
            }else {
                return;
            }
        }
        TreeNode newTreenode=new TreeNode(val);
        if (parent.val > val) {
            parent.left=newTreenode;
        }else {
            parent.right=newTreenode;
        }
    }
    public void remove(int val){
        if (root==null){
            return;
        }
        TreeNode cur=root;
        TreeNode parent=null;
        while (cur!=null){
            if (cur.val>val){
                parent=cur;
                cur=cur.left;
            }else if (cur.val<val){
                parent=cur;
                cur=cur.right;
            }else {
                removeNode(cur,parent);
                return;
            }
        }
    }

    private void removeNode(TreeNode cur, TreeNode parent) {
         if (cur.left==null){
             if (cur==root){
                 root=cur.left;
             }else if (cur==parent.left){
                 parent.left=cur.right;
             }else {
                 parent.right=cur.right;
             }
         }else if (cur.right==null){
             if (cur==root){
                 root=cur.right;
             }else if (cur==parent.left){
                 parent.left=cur.left;
             }else {
                 parent.right=cur.left;
             }
         }else {
             TreeNode taget=cur.right;
             TreeNode tagetPrent=cur;
             while (taget.left!=null){
                 tagetPrent=taget;
                 taget=taget.left;
             }
             cur.val=taget.val;
             if (taget==tagetPrent.left){
                 tagetPrent.right=taget.right;
             }else {
                 tagetPrent.left=taget.right;
             }
         }
    }
}
